package com.fang.algorithm.zuo.basis;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 局部最小问题
 * 无序数组且不相等，任意相邻的两个数满足a < b，则a称之为局部最小
 * @date 2022/7/30 6:19 下午
 **/
public class BinarySearch3 {
    public static void main(String[] args) {
        int[] arr = new int[]{111, 12, 13, 3, 13, 113, 4, 15, 26, 39, 11, 12, 14};
        int index = localMin(arr);
        System.out.println(index);
    }

    private static int localMin(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        // 临界值问题：0位置或者n-1位置只要和相邻位置比较即可得出结论
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1, right = arr.length - 2;
        while (left < right) {
            int mid = (right + left) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                System.out.println(arr[mid]);
                return mid;
            }
        }
        return left;
    }

}
